\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex


\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\rmder#1{{\ \buildrell  \Longrightarrow \over{rm}}^{#1}\ }
\def\lmder#1{\buildrel #1\over{\buildrell  \Longrightarrow \over{lm}}}
\def\Res{\mathrm{Res}}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 6\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{ \{jianchan,sanjian,yemingf\}}@\itshape{cis.upenn.edu}
\end{center}

\vspace {0.25cm}\noindent

\noindent{\bf Solution B1}\

\begin{itemize}
\item Prove that every standard PDA $P_1$ can be converted to a
shift-reduce PDA $P_2$:\
    \begin{enumerate}
    \item First, convert $P_1$ to an equivalent one which contains a
    bottom-marker until the very end, by converting each
    $(q,\gamma)\in\delta(p,a,Z_0)$ to $(q,\gamma Z_0)\in
    \delta(p,a,Z_0)$.

    \item For each POP move in $P_1$ like $(q,\epsilon)\in\delta(p,a,Z)$,
    we can simulate it using an extended pop move in $P_2$:
    $(q,\epsilon)\in\delta(p,a,\gamma)$, where $\gamma=Z$.


    \item For each move in $P_1$ like $(q,\gamma)\in(p,a,Z)$ $(\gamma=Y_1Y_2\cdot\cdot\cdot Y_n, n\ge 1)$, we can simulate it using the following moves from
    $P_2$:
        \begin{itemize}
        \item POP $Z$ (since there is always a bottom-marker when this is not a final move, we can always perform the following PUSH moves.)
        \item PUSH $Y_1$
        \item PUSH $Y_2$
        \item $\cdot\cdot\cdot$
        \item PUSH $Y_n$
        \end{itemize}
    \end{enumerate}

In all, we simulate every move in $P_1$ using moves in $P_2$, therefore converted $P_1$ to $P_2$.
    
\item Prove that every shift-reduce PDA $P_2$ can be converted to a
standard PDA $P_1$:
    \begin{enumerate}
    \item For each PUSH move in $P_2$: $(q, YZ)\in\delta(p, a, Z)$,
    simulate it with a move from $P_1$: $(q, \gamma)\in\delta(p, a,
    Z)$, where $\gamma=YZ$.

    \item For each extended POP move in $P_2$: $(q,
    \epsilon)\in\delta(p, a, \gamma)$ $(\gamma=Y_1Y_2\cdot\cdot\cdot Y_n, n\ge 1)$, simulate it
    with the following POP moves from $P_1$:
        \begin{itemize}
        \item $(x_1, \epsilon)\in\delta(p, a, Y_1)$
        \item $(x_2, \epsilon)\in\delta(x_1, \epsilon, Y_2)$
        \item $\cdot\cdot\cdot$
        \item $(q, \epsilon)\in\delta(x_{n-1}, \epsilon, Y_n)$,
        where $x_1,x_2,\cdot\cdot\cdot,x_{n-1}$ are new states added to $P_1$.
        \end{itemize}
    \end{enumerate}


In all, we simulate every move in $P_2$ using moves in $P_1$, therefore converted $P_2$ to $P_1$.

\end{itemize}

\vspace{0.25cm}
\noindent
{\bf Solution B2.}\\

Following the definition of primitive recursive for $\mapdef{f}{\Sigma^*}{\Sigma^*}$,
the prove is quite straight forward.\\
Given $f(w) = a_1^{|w|}$, we have,\\
$$f(\epsilon) = a_1^0 = \epsilon,$$
$$f(ua) = a_1^{|ua|} = a_1^{|u|+1} = a_1a_1^{|u|} = a_1f(u),\forall a \in \Sigma.$$
Notice we have reached the standard form of the definition of primitive recursion, where 
$$h_1(u,f(u)) = \cdots = h_N(u,f(u)) = a_1f(u),$$
and $\forall u \in \Sigma^*,$
$$f(\epsilon) = \epsilon,$$
$$f(ua_1) = h_1(u,f(u)),$$
$$\cdots = \cdots,$$
$$f(ua_N) = h_N(u,f(u)),$$
Hence by definition, the function $f$ is primitive recursive.\\
\vspace{0.5cm}

\noindent{\bf Solution B3}\\

We will prove that the following properties are non-trivial,
therefore by Rice's theorem, they are undecidable. For each
property, we give two partial recursive functions, one of which
holds for the property while the other does not, or they together
show that the property does not hold.
\begin{enumerate}
    \item $f(x)=1$ and $g(x)=x$
    \item $\varphi_x(x)=x$ and $\varphi_y(x)=2*x$
    \item If $\varphi_x(x)=\varphi_a(x)$, then $\varphi_y(x)=2*\varphi_x(x)\ne
    \varphi_a(x)$.
    \item $f(x)=$ undefined $(x=\{1,2\})$ and $g(x)=1$ $(x=1)$,
    $g(x)=$ undefined $(x=2)$
\end{enumerate}
The above examples can show that the properties they represent are
non-trivial. Therefore by Rice's theorem, these properties are
undecidable.\\

\vspace {5cm}
\noindent
{\bf Solution B4.}\\

The big idea is deriving a relationship between $A(n,x+1)$ and $A(n,x)$, 
then doing math induction on $x$ to prove the general form of $A(n,x)$, where $n$ is a given integer. 
For convenience, let's mark the three definition equations of Ackermann's function as,
\[\eqaligneno{
A(0,\, y) &= y + 1 \cdots def(1)\cr
A(x + 1,\, 0) &= A(x,\, 1) \cdots def(2)\cr
A(x + 1,\, y + 1) &= A(x,\, A(x + 1, y)) \cdots def(3)\cr
}\]

\begin{enumerate}
  \item Prove $A(0,\, x) = x + 1$.\\
  By def(1), it follows immediately that $A(0,\, x) = x + 1$.
  \item Prove $A(1,\, x) = x + 2$.\\
  By def(3), $A(1,\ x + 1) = A(0,\ A(1,\ x)) = A(1,\ x)+1$.\\ Doing math induction on $x$.
   \begin{itemize}
    \item Base case $x = 0$. By def(1) and (2), $A(1,\ 0) = A(0,\ 1) = 2 = x + 2$. Proved.
    \item Induction step. Assume $A(1,\ x) = x + 2$.\\ 
    Then $A(1,\ x + 1) = A(1,\ x) + 1 = x + 2 + 1 = (x+1) + 2$. Proved.   
   \end{itemize}
  Hence, $A(1,\, x) = x + 2, \forall x \in N$.
  
  \item Prove $A(2,\ x) = 2x + 3$\\
  By def(3) and what we just proved in 2,\\ 
  $A(2,\ x+1) = A(1,\ A(2,\ x)) = A(2,\ x)+2$.\\ Doing math induction on $x$.
   \begin{itemize}
    \item Base case $x = 0$. By def(2) and 2, $A(2,\ 0) = A(1,\ 1) = 3 = 2x + 3$. Proved.
    \item Induction step. Assume $A(2,\ x) = 2x + 3$.\\ 
    Then $A(2,\ x + 1) = A(2,\ x) + 2 = 2x + 3 + 2 = 2(x+1) + 3$. Proved.   
   \end{itemize}
  Hence, $A(1,\, x) = 2x + 3, \forall x \in N$.
  
  \item Prove $A(3,\ x) = 2^{x+3} - 3$\\
  By def(3) and what we just proved in 3,\\
  $A(3,\ x+1) = A(2,\ A(3,\ x)) = 2A(3,\ x)+3$.\\ Doing math induction on $x$.
  \begin{itemize}
    \item Base case $x = 0$. By def(2) and 3, $A(3,\ 0) = A(2,\ 1) = 2*1 + 3 = 2^{0+3} - 3$. Proved.
    \item Induction step. Assume $A(3,\ x) = 2^{x+3} - 3$.\\ 
    Then $A(3,\ x + 1) = 2A(2,\ x) + 3 = 2*(2^{x+3} - 3) + 3 = 2^{(x+1)+3} - 3$. Proved.   
   \end{itemize}
  Hence, $A(3,\ x) = 2^{x+3} - 3, \forall x \in N$.
  
  \item Prove $A(4, x) = \supexpo{2}{2}{x+3}\> - 3.$\\
  By def(3) and what we just proved in 4,\\
  $A(4,\ x+1) = A(3,\ A(4,\ x)) = 2^{A(4,\ x) + 3} - 3$.\\ Doing math induction on $x$.
  \begin{itemize}
    \item Base case $x = 0$. By def(2) and 4, $A(4,\ 0) = A(3,\ 1) = 2^{1+3} - 3 = \supexpo{2}{2}{0+3}\> - 3$. Proved.
    \item Induction step. Assume $A(4,\ x) = \supexpo{2}{2}{x+3}\> - 3.$\\ 
    Then $A(4,\ x + 1) = 2^{A(4,\ x) + 3} - 3 = 2^{\supexpo{2}{2}{x+3}\> - 3 + 3} - 3 = \supexpo{2}{2}{(x+1)+3}\> - 3$. Proved.   
   \end{itemize}
  Hence, $A(4, x) = \supexpo{2}{2}{x+3}\> - 3, \forall x \in N$.

\end{enumerate}


\vspace {0.25cm}
\noindent{\bf Solution B5}\\

First, we show the detail of how to simulate a RAM program with two registers using a single register.\\

We store the content of the two registers $r_1, r_2$ in one register as the form $r_1\#r_2$, using a new marker $\#$.\\

We firstly give two RAM program: $SWAP$, $ r_2\#r_1 = SWAP( r_1\#r_2 ) $; $CLEAR$, $ \#r_2 = CLEAR( r_1\#r_2 ) $. Let us assume the alphabet is $\{a_1, \cdots , a_n\}$.

\begin{table}[ht]
	\begin{center}
		\begin{tabular}{ c  c  c c }
			 & & $add_\#$ & $R1$ \\
			$N0$ & $R_1$ & $jmp_{a_1}$ & $N1b$ \\
			& $\cdots$ & $\cdots$ & $\cdots$ \\
			& $R_1$ & $jmp_{a_i}$ & $Nib$ \\
			& $\cdots$ & $\cdots$ & $\cdots$ \\
			& $R_1$ & $jmp_{a_n}$ & $Nnb$ \\
			& $R_1$ & $jmp_{\#}$ & $Mb$ \\
			$N1$ & & $add_{a_1}$ & $R1$ \\
			 & & $tail$ & $R1$ \\
			 & & $jmp$ & $N0a$ \\
			& $\cdots$ & $\cdots$ & $\cdots$ \\
			$Ni$ & & $add_{a_i}$ & $R1$ \\
			 & & $tail$ & $R1$ \\
			 & & $jmp$ & $N0a$ \\
			& $\cdots$ & $\cdots$ & $\cdots$ \\
			$Nn$ & & $add_{a_n}$ & $R1$ \\
			 & & $tail$ & $R1$ \\
			 & & $jmp$ & $N0a$ \\
			$M$ & & $tail$ & $R1$ \\
			 & & $continue$ &  \\
			
		 \end{tabular}
		 \caption{SWAP RAM Program \label{table:SWAP}}
	 \end{center}
 \end{table}

\begin{table}[h!t]
	\begin{center}
		\begin{tabular}{ c  c  c c }
			$N$ & $R_1$ & $jmp_{\#}$ & $Mb$ \\
			& & $tail$ & $R1$ \\
			& & $jmp$ & $Na$ \\			
			$M$ & & $continue$ &  \\
		 \end{tabular}
		 \caption{CLEAR RAM Program \label{table:CLEAR}}
	 \end{center}
 \end{table}

Then we give out the simulation of the basic instruction set:\\

(1) $N \ add_{a_i} \ R_1$ becomes:

\begin{center}
$N$ $SWAP$ $R_1$ \\
$add_{a_i}$ $R_1$ \\		
$SWAP$ $R_1$ \\
\end{center}

(2) $N \ add_{a_i} \ R_2$ becomes:

\begin{center}
$N \ add_{a_i} \ R_2$
\end{center}

(3) $N \ tail \ R_1$ becomes:

\begin{center}
$N$ $tail$ $R_1$ \\
\end{center}

(4) $N \ tail \ R_2$ becomes:

\begin{center}
$N$ $SWAP$ $R_1$ \\
$tail$ $R_1$ \\		
$SWAP$ $R_1$ \\
\end{center}

(5) $N \ clr \ R_1$ becomes:

\begin{center}
$N$ $CLEAR$ $R_1$ \\
\end{center}

(6) $N \ clr \ R_2$ becomes:

\begin{center}
$N$ $SWAP$ $R_1$ \\
$CLEAR$ $R_1$ \\		
$SWAP$ $R_1$ \\
\end{center}

(7) $N \ R_1 \ jmp_{a_j} \ N1a$ and $N \ R_1 \ jmp_{a_j} \ N1b$ remain the same.\\

(8) $N \ R_2 \ jmp_{a_j} \ N1a$ and $N \ R_2 \ jmp_{a_j} \ N1b$ becomes the following respectively:

\begin{center}
$N$ $SWAP$ $R_1$ \\
$R_1$ $jmp_{a_j}$ $N1a$ \\		
$SWAP$ $R_1$ \\
\end{center}

\begin{center}
$N$ $SWAP$ $R_1$ \\
$R_1$ $jmp_{a_j}$ $N1b$ \\		
$SWAP$ $R_1$ \\
\end{center}

(9) $N \ jmp \ N1a$, $N \ jmp \ N1b$ and $N \ continue $ remain the same.\\

It is easy to see that by applying the same method recursively for $n-1$ times, we can simulate a RAM program with $n$ registers using a single register.\\

With above, we can conclude that a RAM program with $p\geq 2$ registers can be simulated by a RAM program with a single register.\\


\vspace{0.25cm}
\noindent{\bf Solution B6}\\

\begin{itemize}
 \item The family of context free languages contains countable number of members. Since, every context-free language is a recursive set, and we can index all the partial recursive functions.
 \item Context free languages are closed under union, for any two context free grammars $G_1,G_2$ with start symbol $S_1, S_2$ respectively, we can easily introduce new start symbol $S$, and new rule $S \rightarrow S_1$, $S \rightarrow S_2$. The new grammar will generate the union of the two context free languages.
 \item Context free languages are closed under concatenation with regular languages. Since regular languages are a subset of context-free languages, we can also write context free grammar $G_R$ for any regular language $R$. Assume the start symbol of a context free grammar $G_C$ is $S_C$, the start symbol of a context free grammar $G_R$ is $S_R$. Then, we can easily introduce new start symbol $S$, and new rule $S \rightarrow S_CS_R$. The new grammar will generate the concatenation of the context free language with the regular language, which is also a context free language. 
 \item If context free grammar $G_R$ generate a regular language $R$, then it is easy to see that $L(G_R)/a = R/a $, and in \textbf{Homework 2 Problem B5}, we already prove that $R/a$ is also regular.
\end{itemize}

By \textbf{Greibach Theorem}, we conclude that the problem above is undecidable.

\vspace{0.25cm}
\vspace{0.25cm}
\noindent
{\bf Solution B7}\\

\noindent
{\bf (i) Proof:}\\

Similar to the proof in the notes \textbf{Section 7.5}, we will show how to construct an instance of the tiling problem with a single initial tile, where $s=max\{2, 2^{p(u)}\}$, and $u \in L, L \in \s{NEXP}$ iff the tiling problem has a solution.\\

Sharing the same idea behind the definition of the tiles: the labels on the horizontal edges between two adjacent rows represent a legal ID $upav$. And the difference is: we need to allow one horizontal edge of a single tile to encode string, instead of just encoding one letter. We also assume that TM $M$ signals that it accepts $u$ by halting with the output 1. The following figure (on the last page) will show all the construction of all type of tiles.\\


With all the building blocks, similar to the proof in the notes, it is not hard to check the conclusion.\\
 
\noindent
{\bf (ii) Proof:}\\

The rough idea is using Rice Theorem, show the original problem correspond to 
an non-trivial property of some Turing Computable function. 
Then because the set of Turing Computable functions is equal to partial recursive functions,
following Rice theorem, any non-trivial input/output
property of such function is undecidable.\\
\begin{itemize}
  \item Recall the problem said for all $s>1$, there is a function $\sigma_s$ tiling the 
  $2s*s$ rectangle. In (i), we already prove that such problem can be reduced from language
  in exponential time bounded of a nondeterministic Turing Machine. So the problem can be reduced from
  the following one:\\
  Given an nondeterministic Turing Machine, for all $s>1$, there is some string $w$ accepted by it
  with exactly $s$ computations.
  \item Next we show the above assertion is actually an non-trivial property of Turing Machine, by
  pointing out there are some Turing Machines hold this property while others do not.\\
  Consider two Turing Machines:\\
  $TM_1$ accepts $\Sigma^*$, and $\forall w \in \Sigma^*$, $TM_1$ accepts it by $|w|$ steps computation.\\
  $TM_2$ accepts $\{\epsilon\}$, it rejects any input.\\ 
  It is trivial to show such two Turing Machines exist because $\Sigma^*$ and $\{\epsilon\}$ are both regular
  and can be accepted by DFA's.
  \item Obviously, $TM_1$ holds the property given any $s>1$, there is some input $w\, |w| = s$ such that it can be 
  accepted by $TM_1$ with $s$ computations. In fact $TM_1$ accepts any input of length $s$ with $s$ computations.\\
  On the other hand, $TM_2$ does not hold the property because it rejects any non-empty input.\\
  Hence, the property is non-trivial and by Rice Theorem, it is undecidable. Since it can be reduced to the 
  original problem stated in the question, we conclude the original problem is also undecidable.
\end{itemize}

\end{document}
